#include "../tools.h"

/**
 * morris 算法，利用叶子节点的空闲指针，实现线性时间复杂度，常量空间
 * 对没有左子树的节点只访问一次，对有左子树的节点访问两次
 * 
 * cur 无左子树，则 cur 向右移动
 * cur 有左子树，找 cur 左子树上最右的点 mostR
 *      mostR 的 right 指向 nullptr，则让其指向 cur，cur 向左移动
 *      mostR 的 right 指向 cur，则让其指向 nullptr，cur 向右移动
 * 
 */

void morris_pre(TreeNode* root){
    if(root == nullptr) return;

    TreeNode* cur = root;       // 当前节点
    TreeNode* mostR = nullptr;  // 当前节点左孩子的最右节点
    while(cur != nullptr){
        mostR = cur->left;
        if(mostR != nullptr){
            // 能往右就往右
            while(mostR->right != nullptr && mostR->right != cur)
                mostR = mostR->right;
            // mostR 右孩子指向空，让其指向 cur，cur 向左移动
            if(mostR->right == nullptr){
                // ! 第一次访问，前序遍历打印
                cout << cur->val << " ";
                mostR->right = cur;
                cur = cur->left;
                continue;
            }
            // mostR 右孩子指向 cur，让其指向空，cur 向右移动
            // 说明cur的左子树已经遍历完了（是第二次遍历到它）
            // 还原链接，检查cur->val，然后遍历右子树
            else
                mostR->right = nullptr;
        }
        else
            // ! 如果cur的左子树不存在，检查cur->val，然后遍历右子树
            cout << cur->val << " ";
        cur = cur->right;
    }
}

void morris_in(TreeNode* root){
    if(root == nullptr) return;

    TreeNode* cur = root;
    TreeNode* mostR = nullptr;
    long long pre = LONG_MIN;
    while(cur != nullptr){
        mostR = cur->left;
        if(mostR != nullptr){
            while(mostR->right != nullptr && mostR->right != cur)
                mostR = mostR->right;
            if(mostR->right == nullptr){
                mostR->right = cur;
                cur = cur->left;
                continue;
            }
            else{ // 恢复
                mostR->right = nullptr;
            }
        }
        cout << cur->val << " ";
        cur = cur->right;
    }

}


int main(int argc, char const *argv[])
{

    vector<int> vec = {5,1,4,7,8,3,6,9};
    TreeNode* tree = create_tree(vec);
    show(tree);

    morris_pre(tree);
    cout << endl;
    morris_in(tree);

    return 0;
}
